#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<stack>
using namespace std;
//bool isMatch(string s, string p) {
//	int n = s.size(), m = p.size();
//	vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
//	s = " " + s, p = " " + p;
//	dp[0][0] = true;
//	for (int j = 1; j <= m; j++)
//	{
//		if (p[j] == '*')
//			dp[0][j] = true;
//		else
//			break;
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			if (p[j] == '*')
//				dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
//			else
//				dp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 1];
//		}
//	}
//	return dp[n][m];
//}
//bool isMatch(string s, string p) {
//	int n = s.size(), m = p.size();
//	vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
//	dp[0][0] = true;
//	for (int j = 2; j <= m; j+=2)
//	{
//		if (p[j] == '*')
//			dp[0][j] = true;
//		else
//			break;
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			if (p[j] == '*')
//				dp[i][j] = dp[i][j - 2] || ((s[i] == p[j - 1] || p[j - 1] == '.') &&
//				 dp[i - 1][j]);
//			else
//				dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i - 1][j - 1];
//		}
//	}
//	return dp[n][m];
//}
//bool isInterleave(string s1, string s2, string s3) {
//	int n = s1.size(), m = s2.size();
//	if (n + m != s3.size())
//		return false;
//	vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
//	s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;
//	dp[0][0] = true;
//	for (int i = 0; i <= n; i++)
//		dp[i][0] = s1[i] == s3[i] && dp[i - 1][0];
//	for (int j = 1; j <= m; j++)
//		dp[0][j] = s2[j] == s3[j] && dp[j - 1][0];
//
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			if (s1[i] == s3[i + j])
//				dp[i][j] = dp[i - 1][j];
//			else if (s2[j] == s3[i + j])
//				dp[i][j] = dp[i][j - 1];
//		}
//	}
//	return dp[n][m];
//}
//
//#include<iostream> 
//using namespace std;
//class B1 {
//public:
//	B1(int i) { cout << "constructing B1" << i << endl; }
//	~B1() { cout << "destructing B1" << endl; }
//};
//class B2 {
//public:
//	B2() { cout <<  "constructing B2" << endl; }
//	~B2() { cout << "destructing B2" << endl; }
//};
//class C : public B2, virtual public B1 {
//	int j; 
//public:
//	C(int a, int b, int c) : B1(a), memberB1(b), j(c) {}
//private:
//	B1 memberB1;
//	B2 memberB2;
//};
//int main() {
//	C obj(1, 2, 3);
//}
//class MinStack {
//public:
//    MinStack() {
//
//    }
//
//    void push(int val) {
//        in.push(val);
//        if (min.empty() || val <= min.top())
//            min.push(val);
//    }
//
//    void pop() {
//        if (in.top() == min.top())
//            min.pop();
//        in.pop();
//    }
//
//    int top() {
//        return in.top();
//    }
//
//    int getMin() {
//        return min.top();
//    }
//    stack<int> in;
//    stack<int> min;
//};
//bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
//    // write code here
//    stack<int> s;
//    int i = 0;
//    for (auto& e : pushV)
//    {
//        s.push(e);
//        while (s.top() == popV[i])
//        {
//            s.pop();
//            i++;
//        }
//    }
//    return s.empty();
//}
//int minimumDeleteSum(string s1, string s2) {
//    int n = s1.size(), m = s2.size();
//    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
//    s1 = ' ' + s1, s2 = ' ' + s2;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//            if (s1[i] == s2[j])
//                dp[i][j] = max(dp[i][j],dp[i - 1][j - 1] + s1[i]);
//        }
//    }
//    int sum1 = 0, sum2 = 0;
//    for (auto& e : s1)
//        sum1 += e;
//    for (auto& e : s2)
//        sum2 += e;
//    return sum1 + sum2 - 2 * dp[n][m];
//}
//int findLength(vector<int>& nums1, vector<int>& nums2) {
//    int n = nums1.size(), m = nums2.size();
//    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
//    int ret = 0;
//    for(int i=1;i<=n;i++)
//        for (int j = 1; j <= m; j++)
//            if (nums1[i] == nums2[j])
//            {
//                dp[i][j] = dp[i - 1][j - 1] + 1;
//                ret = max(ret, dp[i][j]);
//            }
//    return ret;
//}
const int N = 1000;
int n, V,v[N],w[N];
int dp[N][N];
int main()
{
	cin >> n >> V;
	for (int i = 0; i < n; i++)
		cin >> v[i] >> w[i];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= V; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= v[i - 1])
				dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);
		}
	}
	cout << dp[n][V]<<endl;

	memset(dp, 0, sizeof(dp));
	for (int j = 1; j <= V; j++)
		dp[0][j] = -1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= V; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= v[i - 1]&& dp[i - 1][j - v[i - 1]]!=-1)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);
		}
	}
	cout << (dp[n][V] == -1 ? 0 : dp[n][V])<<endl;

	return 0;
}